This application is related in general to VLSI CAD design, and in specific to an apparatus and method for representing designs in an occurrence model that eliminates duplicate data about the system thereby reducing the memory usage for the design.
Prior computer aided design (CAD) systems represent designs in a hierarchical connectivity form that provides design information to system designers with different levels of abstraction. An example of such a schematic configuration 100 is shown in FIG. 1, which depicts the relationships between a cell 101, a port 102, a net 103, an instance 104, and a port instance 105. Such a configuration is known as a folded connectivity model. The cell block 101 describes a device or structure of the system, e.g. a full adder. A cell contains collections of instances of other cells, nets (which are wires) and the external interfaces to the cell (ports). The net block 103 describes the wires that make up the internal connections within the cell block. The port block 102 describes the interface to the cell and provides the connection points for the nets (wires) to carry signals into and out of the cell block""s logic.
As stated above, a cell block provides the definition of a device or structure. Once a cell has been defined, it can then be instantiated (wherein an instance block 104 is created of that cell), so that it may be used in other cell definitions. In this way, a design hierarchy can be created. The instance block describes the devices or structures used to form the functionality of a cell, e.g., for a two bit adder: two full adder cell instances are created. Just as an instance records the instantiation (or use of) a cell block, the port instance block 105 records the instantiation of the ports on the cell. The port instances allow us to record the specific nets that are connected to a given instance.
The hierarchical nature of the information stored in the folded connectivity model is shown by way of example only in FIGS. 2A-2C. FIG. 2A depicts the highest level of hierarchy, that is cell block 200, which is a two bit adder. The two bit adder block has 8 ports (the inputs A1, B1, A0, B0, Cin; and the outputs Cout, S1, and S0). It contains the nets that are connected to these ports (A1, B1, A0, B0, Cin, Cout, S1, and S0), in addition to one internal net (Coxe2x80x94carry) which is not connected to a port on the cell boundary, but is none-the-less a net contained within the two bit adder cell definition. Finally, the two bit adder contains two instances, FA0 block 202 and FA1 block 203, each of which are instances of a full adder (or a one-bit adder).
FIG. 2B depicts the next lower level of the hierarchy of the system, showing the cell definition for the full adder. Note that the instances FA0 (block 202) and FA1 (block 203) in the top level (FIG. 2A) are described by a cell at the next lower level of hierarchy. The full adder block 202 has 5 ports (input ports A, B, and Cin; the output ports S and Co). It also contains 11 nets (ported nets A, B, Cin, Col and S; internal nets sig_1, sig_2, sig_3, sig_4, sig_5, and sig_6), and 8 instances (2 instances of an inverter, I1, and I2; 2 instances of a 2-input NOR gate, NO1, NO2; 2 instances of a 2-input XOR gate, XO1 and XO2; and 2 instances of a 2-input NAND gate, NA1 and NA2). Finally, FIG. 2C depicts one of the cells at the lowest level of hierarchy, the 2-input NAND gate (205). Note that there are 3 other types of cells at this same level of hierarchy that are not depicted (namely the inverter, the 2-input NOR gate, and the 2-input XOR gate). Additional levels of hierarchy may exist, e.g. a level higher than FIG. 2A and/or lower than FIG. 2C.
A folded connectivity model provides a memory efficient representation of source VLSI design data as seen by the VLSI designer. A fundamental limitation of the folded connectivity model, however, is its ability to represent a truly unique addressable object for each object created across the many levels of design hierarchy. Although this is not an issue for many existing CAD tools, it is becoming more of an issue for the next generation analysis and design tools which need to analyze design entities that span the hierarchy.
The design of FIGS. 2A-2C can be walked through to illustrate the fundamental limitation of a folded connectivity model. In these FIGURES, the top level cell FIG. 2A contains two instances of the cell xe2x80x9cfull_adderxe2x80x9d, FA0 and FA1. Each cell xe2x80x9cfull_adderxe2x80x9d contains two instances of the block xe2x80x9cnandxe2x80x942xe2x80x9d, NA1 and NA2. This information is recorded in the folded connectivity model as shown in FIG. 4. Notice that, in this diagram, there is only one cell 406 for the NA1 and NA2 instances (blocks 415 and 405 respectively). But, when the same design in the form shown in FIG. 3 is viewed, there are in reality, two different occurrences of the instance NA1 (FA0/NA1 and FA1/NA1). The same is true for the instance NA2. The folded connectivity model only records that a single instance of cell xe2x80x9cnandxe2x80x942xe2x80x9d named NA1 is an element of the cell xe2x80x9cfull_adderxe2x80x9d. For another example, only one set of information for the Y net will be stored in the folded model, however, each occurrence copy of the Y net is different, e.g., each copy has different delays and/or parasitic effects because, for example, of the different placement for each Y net. However, the folded model does not store these differences, and thus will not support accurate analysis of the design.
A common technique used to avoid this problem is to perform a xe2x80x98flatteningxe2x80x99 process. The process of flattening a hierarchical design removes all intermediate levels of hierarchy, so only primitive elements exist. There are two primary problems with flattening. First, flattening uses a great deal of computer memory. With today""s microprocessor designs, it is impossible to flatten the entire hierarchy. The second problem is that flattening is a one-way process. Once flattened, it is impossible to relate flattened circuit elements back to a hierarchical view.
For these reasons, the occurrence (or unfolded) model representation is becoming a more important representation for many of todays CAD tools. FIG. 9 represents a typical occurrence model. In an occurrence model, each and every cell is stored, including those cells that are duplicated, while retaining the notion of the original design hierarchy. The primary advantage of an occurrence model is that it allows tools to obtain the benefits of flattening (being able to see a flattened view of the design and the interconnecting nets that span hierarchy) without losing hierarchical information. In addition, using an occurrence model gives some flexibility to the tool developer, so that they do not have to build a model to represent the entire design. Instead the model represents only those pieces currently being evaluated.
For example, as shown in FIG. 3, each adder 202 and 203 is stored separately in the model, as well as each second NAND (N2) circuit 205, 208 or each adder, and each N2 transistor 207, 209 of N2 circuit. FIG. 3 depicts the multi-level view of the cell of FIG. 1 with the different levels of the example of FIGS. 2A-2C. (Note that for simplicity, the other elements of the circuit, as well as the sub-elements, e.g., I1 and I2 are not shown.) However, modern IC circuits, e.g., processors, comprise millions of instances. Thus, the size of the model quickly becomes very large as more lower levels are added to the model. Current computer systems do not have adequate memory to store the complete occurrence model. However, the lower levels are becoming more important to designers. The presence of the lower levels in the model allows for more detailed analysis of the system, e.g., analyzing parasitic loss from the net connections, which allows the designer to improve the speed and efficiency of the system.
Note that the large memory requirements of the occurrence model come not only from the storage of every instance in the design, but also from the storage of the names of each instance. For example, a typical design may include 40,000,000 P transistors, each of which requires a unique hierarchical name. For the arrangements of FIGS. 2A-2C and 3, hierarchical names for the P transistor 207 could be 2bitadd/fa0/na2/p2. Thus, as additional layers are used, the hierarchical names grow longer until they possibly exceed the size of the cells being labeled with the names.
Designers may use hash tables to store some unique occurrence information that is not stored in the folded model. Such tables are not part of the folded model and are stored separately from the model. Tables are created by the designers and include information that designer is interested in using in the analysis of the design. However, models that use these tables are not memory efficient and tend to run slow because of poor homemade designs. Also, the tables are transient. They are maintained only for the analysis of interest and then discarded. This is because each device needs its own hash table. Thus, only a small part of the design can be examined at one time. The biggest problem with homemade hash tables is that they are not reusable.
The present invention is directed to a system and method that defines a light weight folded occurrence model which includes aspects of both the folded model and the occurrence model.
The inventive lightweight occurrence model uses the arrangement of the folded model but includes occurrence nodes that are associated with the folded model. There is at least one occurrence node for each instance of an object type in the model. Each occurrence node includes occurrence specific data or a pointer to such data, a pointer to a parent/owner occurrence node, and a pointer to a folded model describer (instance net. etc.). Thus, most of the information that is present in a full occurrence model can be included in the inventive lightweight occurrence model. Since the inventive occurrence model is smaller than the full occurrence model, the entirety of complex circuit designs, e.g., microprocessors, can be represented by the inventive lightweight occurrence model. Thus, low level characteristics of the design, e.g., timing delays, can be examined.
The pointers, or other abstract interfaces, allow the information of the nodes of the folded model to be altered to include the unique data of the occurrence model instances, including its hierarchical location in the model. Thus, the entirety of the full occurrence model can be represented by the inventive lightweight occurrence model, depending upon the amount of specific data associated with the node (either stored in the node or pointed to by the node). Note that the occurrence node names do not have to be stored in the nodes. The name of the node, if needed for analysis and not stored, can be constructed from information in the inventive light weight occurrence model. Note that the occurrence nodes do not store information that is already present in the folded model, e.g., information on child nodes and/or information about the relationships of ports, cells, and nets. Consequently, the memory required for the inventive lightweight occurrence model is significantly less than that required for the full occurrence model. For example, an inventive node storing only three pointers may require 12 bytes, while a full occurrence node may require 40 or more bytes, meaning that the inventive lightweight occurrence model would only require about 30% of the memory required for the full occurrence model.
Another aspect of the present invention is that the lightweight occurrence model may be controlled by a user. The user may control the model so that only a desired level of hierarchy for a desired portion of the model is created. In the prior art, the full occurrence model forces the folded model to be unfolded to the lowest level of the model. Note that this allows the model to have more detailed (lower level) information stored for a particular portion, while having less detailed (higher level) information stored for the remainder of the model. This allows a partial tree to be used, with some branches having more detailed information than other branches.
Alternatively, the user may have a choice of creating an occurrence tree that only contains 1) occurrence node for instance, 2) occurrence node for instance and net, or 3) occurrence node for instance, net and port instance etc. so that based upon what kind of information the user is interested in, the user may have the total control of what size of the occurrence tree he may want to create.
As stated above, the occurrence node names do not have to be stored in the nodes. However, the model needs to work with tools that require node names for performing analysis on the designs that use the model. Typically, the analysis is a hierarchical-based analysis, and hierarchical names are required. However, in the invention, the names of the nodes can be constructed from information in the inventive lightweight occurrence model, e.g., the owner node pointers, the folded instance pointers, etc. This is one of the ways that the inventive lightweight occurrence model appears to the user to be a full occurrence model.
The inventive lightweight occurrence model maintains the occurrence specific information in a more permanent and organized manner than that of the prior art. The hash tables used by the prior art are external from the model. The hash tables are also written by a designer for their own use and are discarded when that use is finished. Information needed at a subsequent time and/or by a different designer is rewritten into a new hash table. Consequently, the use of hash tables results in error-prone and inconsistent analysis. Thus, the specific information for the inventive model needs only to be written once and is maintained with the inventive model.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claim of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims. The novel features that are believed to be characteristic of the invention, both as to its organization and method of operation, together with further objects and advantages will be better understood from the following description when considered in connection with the accompanying figures. It is to be expressly understood, however, that each of the figures is provided for the purpose of illustration and description only and is not intended as a definition of the limits of the present invention.